/*
 * 百度在线网络技术（北京）有限公司拥有本软件版权2022并保留所有权利。
 * Copyright 2022, Baidu.com,Inc 2:Baidu Online Network Technology (Beijing) Co.,Ltd,
 * All rights reserved.
 */

package com.azdebugit.suanfa.test.teshuawei.test.双指针;

/**
 * Title：NC22-合并2个有序数组, 不能开辟额外的空间，结果存放在A数组中
 * Description：双指针
 * @author WZQ
 * @version 1.0.0
 * @date 2021/3/3
 */
public class NC22 {

    public static void merge(int A[], int m, int B[], int n) {
        //双指针，纪录2个集合确定合并的位置
        int a = 0, b = 0, temp = 0;
        while (a < (m+n) && b < n){
            //小于，A[a]位置不变
            while (a < (m+b) && A[a] < B[b]){
                a ++;
            }
            //等于，大于，A[a]后未判断的全体后退
            if (m + b - a >= 0) System.arraycopy(A, a, A, a + 1, m + b - a);
//            for (int i = m+b-1; i>=a; i--) {
//                A[i+1] = A[i];
//            }
            //B[b]放到A[a]位置
            A[a] = B[b];
            a ++;
            b ++;
        }
        for ( int s : A) {
            System.out.print(s);
        }
    }

    /**
     * 1 3 7
     * 1 5 6
     * 1 1 3 5 6 7
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 7, 0, 0, 0};
        int[] arr2 = {1, 5, 6};
        merge(arr1, arr1.length/2, arr2, arr2.length);
    }

}
